\documentclass[a4paper]{article}
\usepackage[affil-it]{authblk}
\usepackage[backend=bibtex,style=numeric]{biblatex}

\usepackage{geometry}
\geometry{margin=1.5cm, vmargin={0pt,1cm}}
\setlength{\topmargin}{-1cm}
\setlength{\paperheight}{29.7cm}
\setlength{\textheight}{25.3cm}

\addbibresource{citation.bib}

\begin{document}
	% =================================================
	\title{Numerical Analysis homework}
	
	\author{LiangYue 3220100159
		\thanks{Electronic address: \texttt{3220100159@zju.edu.cn}}}
	\affil{(Information and Computing Science 2201), Zhejiang University }
	
	
	\date{Due time: \today}
	
	\maketitle
	
	\begin{abstract}
	%	The abstract is not necessary for the theoretical homework, 
%		but for the programming project, 
	%	you are encouraged to write one.      
	\end{abstract}
	% ============================================
	\section*{I.}
	\subsection*{I-a.}
	\(f(x)=\frac{1}{x},x_0=1,x_1=2,f^{'}(x)=-\frac{1}{x^{2}},f^{''}(x)=\frac{2}{x^{3}}\)\\
	Firstly,we have the linear interpolation for f(x) at $x_0=1,x_1=2$:
	\[P_1(f;x)=f(x_0)+\frac{f(x_0)-f(x_1)}{x_0-x_1}(x-x_0).\]
	So with the question,\(f(x)-P_1(f;x)=\frac{f^{''}(\xi(x))}{2}(x-x_0)(x-x_1)=f(x)-f(x_0)-\frac{f(x_0)-f(x_1)}{x_0-x_1}(x-x_0).\)Simplifying this expression yields,we have
	\[\frac{1}{x}+\frac{1}{2}x-\frac{3}{2}=\frac{(x-1)(x-2)}{(\xi(x))^{3}}.\]
	So \[\xi(x) = (2x)^{\frac{1}{3}}\].
	\subsection*{I-b.}
	Clearly, \(1 \leq \xi(x) \leq 2\).\\
	Taking the derivative of \(\xi(x)\),we know it is increasing easily.So \(\xi(x)\) reaches the maximum $2^{\frac{2}{3}}$ and minimum $2^{\frac{1}{3}}$ respectively at x=2 and x=1.\\
	As for the maximum of \(f''(\xi(x))\), \(f''(\xi(x))=\frac{1}{x}\)(decreasing), reaches its maximum at x=1 where the value is 1.
	\section*{II.}
	Use Lagrange formula.Let \(l_k=\prod_{i\ne k;i=0}^{n}\frac{x-x_i}{x_k-x_i},P_n(x)=\sum_{K=0}^{n}f_kl_k\);\\
	To ensure $P_n(x)$ is non-negative,we can decompose it into a non-negative part and a negative part, and multiply the negative part by a positive number less than 1, which ensures that the new polynomial is still close to the original interpolation point and remains non-negative.
	
	\section*{III.}
	\subsection*{III-a.}
	When n=0,by the definition of divided differences,\(f[t]=f(t)=e^{t}=\frac{(e-1)^0}{0!}e^{t}\);\\
	Assume that the conclusion is right for n-1,which means \(f[t,t+1,...,t+n-1]=\frac{(e-1)^{n-1}}{(n-1)!}e^{t}\);\\
	We know that \(f[t,t+1,...,t+n]=f[t+1,t+2,...,t+n]-f[t,t+1,...,t+n-1]\);
	Let t=t+1,so \(f[t+1,t+2,...,t+n]=\frac{(e-1)^{n-1}}{(n-1)!}e^{t+1}\) informed from the above. With \(f[t,t+1,...,t+n-1]=\frac{(e-1)^{n-1}}{(n-1)!}e^{t}\),we have
	\[f[t,t+1,...,t+n]=\frac{\frac{(e-1)^{n-1}}{(n-1)!}e^{t+1}-\frac{(e-1)^{n-1}}{(n-1)!}e^{t}}{n}\]
	\[=\frac{(e-1)^{n-1}(e-1)e^{t}}{n(n-1)!}\]
	\[=\frac{(e-1)^{n}e^t}{n!}\]
	\subsection*{III-b.}
	In III-a,we have 	\[f[t,t+1,...,t+n]=\frac{(e-1)^{n}e^t}{n!}\].Let $t=0$,then
	\[\frac{1}{n!}f^{(n)}(\xi)=\frac{(e-1)^{n}}{n!}\]
	For \(f(x)=e^{x},f^{(n)}(x)=e^{x}\),so we have
	\[e^{\xi}=(e-1)^{n}\]
	\[\xi=ln((e-1)^{n})\]
	\[\xi=nln(e-1))\]
	Now consider the location of $\xi$.That is to compare the sizes of $e-1$ and $\sqrt{e}$.$e-1$ $\approx$ 1.718,$\sqrt{e}\approx 1.649$,so $\xi$ is located to the right of the midpoint $\frac{n}{2}$.	
	\section*{IV.f(0)=5,f(1)=3,f(3)=5,f(4)=12}
	\subsection*{IV-a.Use the Newton formula to obtain $p_3(f;x)$; }
	\(f'(x)=7x^{6},f''(x)=42x^{5}.\)
	\(x_0=0, f[x_0]=5\)\\
	\(x_1=1, f[x_1]=3, f[x_0,x_1]=-2 \)\\
	\(x_2=3, f[x_2]=5, f[x_1,x_2]=1, f[x_0,x_1,x_2]=1\)\\
	\(x_3=4, f[x_3]=12,f[x_2,x_3]=7, f[x_1,x_2,x_3]=2, f[x_0,x_1,x_2,x_3]=\frac{1}{4}\)\\
	\[p_3(f;x)=5-2x+x(x-1)+\frac{1}{4}x(x-1)(x-3)\]
	\[p_3(f;x)=\frac{1}{4}x^{3}-\frac{9}{4}x+5\]
	\subsection*{IV-b.}
	\(p_3^{'}(f;x)=\frac{3}{4}x^{2}-\frac{9}{4}=0;\)\\
	\(p_3^{''}(f;x)=\frac{3}{2}x=0;\)\\
	We have x=$\pm \sqrt{3}$,  \(p_3^{'}(f;x)=0\);\\
			x=0,  \(p_3^{''}(f;x)=0;\)\\
	Easily we know $p_3(x)$ reaches the minimum at x=$\sqrt{3}$.\\That is,a approximate value for the location $x_{min}$ of the minimum is $\sqrt{3}$.
	
	\section*{V.\(f(x)=x^{7}\)}
	
	\subsection*{V-a.}
	\(0, 0\)\\
	\(1, 1, 1\)\\
	\(1, 1, 7, 6\)\\
	\(1, 1, 7, 21, 15\)\\
	\(2 ,128 ,127 ,120 ,99, 42\)\\
	\(2 ,128 ,448 ,321 ,201 ,102 ,30\)\\
	So \(f[0,1,1,1,2,2]=30\).\\
	\subsection*{V-b.}
	By the question, we have
\[ f[0,1,1,1,2,2] = \frac{f^{(5)}(\xi)}{5!}. \]
Given that \( f^{(5)}(x) = \frac{7! x^2}{2} \), this means
\[ f^{(5)}(x) = 2520 x^2. \]
Therefore,
\[ 2520 \xi^2 = 30. \]
Solving for \(\xi\), we get
\[ \xi = \sqrt{\frac{30}{2520}}= \sqrt{\frac{10}{7}} \approx 1.20. \]
	\section*{VI.}
	\subsection*{VI-a.}
	\(0, 1\)\\
	\(1, 2, 1\)\\
	\(1, 2, -1, -2\)\\
	\(3, 0, -1, 0, \frac{2}{3}\)\\
	\(3, 0,  0, \frac{1}{2}, \frac{1}{4},-\frac{5}{36}\)\\
	So \(P(x)=1+x-2x(x-1)+\frac{2}{3}x(x-1)^{2}-\frac{5}{36}x(x-1)^{2}(x-3).\)
	\(f(2)=\frac{11}{18}\).
	\subsection*{VI-b.}
	We know \(f(x)-P(f;x)=\frac{f^{(n+1)}(\xi)}{(N+1)!}prod_{i=0}^{k} (x-x_i)^(m_i+1)\).
	So remainder there = \[\frac{f^{(5)}(\xi)x(x-1)^{2}(x-3)^{2}}{6!}\].
	For \(|f^{(5)}(x)|\le M\),remainder $\le$ \(\frac{M(x^{4}-4x^{3}-2x^{2}+12x+9)}{5!}\) on[0,3].So the maximum possible error is $\frac{2}{15}M$ where x=1.
	\section*{VII.}
	Prove it by induction. \\
	For the forward difference :\\
	When k=1, we have \(\bigtriangleup f(x) = f(x+h)-f(x)=1!h^{1}f[x_0,x_1]\);\\
	Assume k=n the equality holds, that is \(\bigtriangleup ^{n}f(x) =n!h^{n}f[x_0,x_1,...x_k]\).\\
	When k=n+1, we have  \(\bigtriangleup ^{n+1}f(x) =\bigtriangleup \bigtriangleup ^{n}f(x)=\bigtriangleup ^{n}f(x+h)-\bigtriangleup ^{n}f(x)\).\\
	\[\bigtriangleup ^{n}f(x+h)-\bigtriangleup ^{n}f(x)=n!h^{n}f[x_0+h,x_1+h,...x_k+h]-n!h^{n}f[x_0,x_1,...x_k]\]
	For \(x_j=x+jh,where \quad j>0\)
	\[=n!h^{n}f[x_1,x_2,...x_{k+1}]-n!h^{n}f[x_0,x_1,...x_k]\]
	By the definition of divided difference, we have
	\[=(n+1)!h^{n+1}f[x_0,x_1,...x_{k+1}]\].\\
	\\
	For the backward definition:\\
	When k=1, we have \(\bigtriangledown f(x) = f(x)-f(x-h)=1!h^{1}f[x_0,x_{-1}]\);\\
	Assume k=n the equality holds, that is \(\bigtriangledown ^{n}f(x) =n!h^{n}f[x_0,x_{-1},...x_{-k}]\).\\
	When k=n+1, we have  \(\bigtriangledown ^{n+1}f(x) =\bigtriangledown \bigtriangledown ^{n}f(x)=\bigtriangledown ^{n}f(x)-\bigtriangledown ^{n}f(x-h)\).\\
	\[\bigtriangledown ^{n}f(x)-\bigtriangledown ^{n}f(x-h)=n!h^{n}f[x_0,x_{-1},...x_{-k}]-n!h^{n}f[x_0-h,x_1-h,...x_k-h]\]
	For \(x_j=x+jh,where \quad j<0\)
	\[=n!h^{n}f[x_0,x_{-1},...x_{-k}]-n!h^{n}f[x_{-1},x_{-2},...x_{-(k+1)}]\]
	By the definition of divided difference, we have
	\[=(n+1)!h^{n+1}f[x_0,x_{-1},...x_{-(k+1)}]\].\\
	
	\section*{VIII.}
	Prove it by induction.\\
	When n=0,\(\frac{\partial}{\partial x_0}f[x_0]=f'(x_0)=f[x_0,x_0]. \)
	Assume when n=k, the equality holds.That is \[\frac{\partial}{\partial x_0}f[x_0,x_1,...,x_n]=f[x_0,x_0,x_1,...,x_n].\]
	So when n=k+1, \\
	\(\frac{\partial}{\partial x_0}f[x_0,x_1,...,x_k,x_{k+1}]\)\\
	\(=\frac{\partial}{\partial x_0}(\frac{f[x_1,x_2,...,x_{k+1}]-f[x_0,x_1,...,x_k]}{x_{k+1}-x_0})\)\\
	\(=\frac{f[x_1,x_2,...,x_{k+1}]}{(x_{k+1}-x_0)^2}+\frac{\partial}{\partial x_0}(\frac{f[x_0,x_1,...,x_k]}{x_0-x_k})\)\\
	\(=\frac{f[x_1,x_2,...,x_{k+1}]}{(x_{k+1}-x_0)^2}+\frac{\frac{\partial}{\partial x_0}f[x_0,x_1,...,x_k](x_0-x_k)-f[x_0,x_1,...,x_k]}{(x_0-x_{k+1})^2}\)\\
	With the assumption for n=k, we have:\\
	\(=\frac{f[x_0,x_1,...,x_{k+1}]}{x_{k+1}-x_0}-\frac{f[x_0,x_0,x_1,...,x_k]}{x_{k++1}-x_0}\)\\
	\(=f[x_0,x_0,x_1,....,x_{k+1}].\)( with the definition of divided difference)
	\section*{IX.}
	Let \(m=min\quad max_{x \in [a,b]}|a_0x^n+a_1x^{n-1}+...+a_n|\).
	By Chebyshev Theorem, we have\[max_{x\in [-1,1]}|\frac{T_n(x)}{2^{n-1}}|\le max_{x\in [-1,1] }|p(x)|\]
	Firstly we should transform x into y to converts its domain to [-1,1].
	Let y=$\frac{x-\frac{a+b}{2}}{\frac{a-b}{2}}$,whose domain is [-1,1].\\
	So \(m=min\quad max_{y \in [-1,1]}|b_0y^n+b_1y^{n-1}+...+b_n|\) now, where \(b_0=(\frac{b-a}{2})^{n}a_0\).\\According to Chebyshev Theorem, \(max_{y \in [-1,1]}|b_0y^n+b_1y^{n-1}+...+b_n|\ge b_0max_{y\in [-1,1]}|\frac{T_n(y)}{2^{n-1}}|=\frac{b_0}{2^{n-1}}=\frac{(\frac{b-a}{2})^{n}a_0}{2^{n-1}}=\frac{(b-a)^n}{2^{2n-1}}a_0\) for \(max|T_n(x)|=1\).
	
	\section*{X.}
	By Theorem 2.45, $T_n(x)$ assumes its extreme n+1 times at the points $x'_k$ (\(x'_k=cos\frac{k}{n}\pi\) ).Suppose \(||\hat{p}_n||_\infty \le ||p||_\infty\) does not hold. We have:
	i.e.\[||\frac{T_n(x)}{T_n(a)}||_\infty \le ||p||_\infty\] 
	With the definition of $||f||_infty$ and $T_n(x)$,
	\[cos(narccos(a))p(x)<T_n(x)\]
	Let \(Q(x)=cos(narccos(a))p(x)-T_n(x)\)
	\[Q(x'_k)=cos(narccos(a)p(x'_k)-T_n(x'_k)\]
	Q(x) has alternating signs at these n+1 points.Hence Q(x) must have n zeros. However the degree of Q(x) is no greater than n-1, so Q(x) $\equiv$ 0.So p(x)=$\frac{T_n(x)}{cos(narccos(a))}$, which implies max \( |p(x)|=\frac{T_n(x)}{cos(narccos(a))}\). It contradicted.
	\section*{XI.}
	proof:\\
	 \[RHS = \frac{n-k}{n}b_{n.k}(t)+\frac{k+1}{n}b_{n,k+1}(t)\]
	 \[=\frac{n-k}{n}\frac{n!}{(n-k-1)!k!}t^{k}(1-t)^{n-k}+\frac{k-1}{n}\frac{n!}{(n-k)!(k+1)!}t^{k+1}(1-t)^{n-k-1} \]
	 \[=\frac{(n-1)!}{(n-k-1)!k!}t^{k}(1-t)^{n-k-1}(1-t)+\frac{(n-1)!}{(n-k-1)!k!}t^{k}(1-t)^{n-k-1}t\]
	 \[=\frac{(n-1)!}{(n-k-1)!k!}t^{k}\]
	 \[=b_{n-1,k}(t)\]
	 \[=LHS\]		
	\section*{XII.}
	proof:\\
	\[\int_{0}^{1} b_{n,k}(t)=\int_{0}^{1}\frac{n!}{(n-k-1)!k!}t^k(1-t)^{n-k} \]
	\[=\frac{n!}{(n-k-1)!k!}B(k+1,n-k+1)\]
	\[=\frac{n!}{(n-k-1)!k!}\frac{\Gamma (k+1)\Gamma(n-k+1)}{\Gamma(n+2)}\]
	\[=\frac{n!}{(n-k-1)!k!}\frac{k!(n-k)!}{(n+1)!}\]
	\[=\frac{1}{n+1}\]
	% ===============================================
	\section*{ \center{\normalsize {Acknowledgement}} }
	Give your acknowledgements here(if any).
	
	
	\printbibliography
	
	If you are not familiar with \texttt{bibtex}, 
	it is acceptable to put a table here for your references.
\end{document}